package com.wuyou.simple;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 1385. 两个数组间的距离值
 */
public class FindTheDistanceValue {


    public static void main(String[] args) {
//        int[] arr1 = {4, 5, 8};
//        int[] arr2 = {10, 9, 1, 8};
        int[] arr1 = {-803,715,-224,909,121,-296,872,807,715,407,94,-8,572,90,-520,-867,485,-918,-827,-728,-653,-659,865,102,-564,-452,554,-320,229,36,722,-478,-247,-307,-304,-767,-404,-519,776,933,236,596,954,464};
        int[] arr2 = {817,1,-723,187,128,577,-787,-344,-920,-168,-851,-222,773,614,-699,696,-744,-302,-766,259,203,601,896,-226,-844,168,126,-542,159,-833,950,-454,-253,824,-395,155,94,894,-766,-63,836,-433,-780,611,-907,695,-395,-975,256,373,-971,-813,-154,-765,691,812,617,-919,-616,-510,608,201,-138,-669,-764,-77,-658,394,-506,-675,523,730,-790,-109,865,975,-226,651,987,111,862,675,-398,126,-482,457,-24,-356,-795,-575,335,-350,-919,-945,-979,611};
        int d = 37;
        System.out.println(sol_2(arr1, arr2, d));
    }


    /**
     * 二分 为什么比暴力破解更慢了 不太明白
     * @param arr1
     * @param arr2
     * @param d
     * @return
     */
    public static int sol_2(int[] arr1, int[] arr2, int d) {
        int res = 0;
        Arrays.sort(arr2);
        for (int i = 0; i < arr1.length; i++) {
            int l = 0, r = arr2.length - 1, mid = 0;
            boolean flag = true;
            while (l <= r) {
                mid = ((r - l) / 2) + l;
                if (Math.abs(arr1[i] - arr2[mid]) > d) {
                    if (arr1[i] - arr2[mid] < 0) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                res++;
            }
        }
        return res;
    }

    public static int sol_1(int[] arr1, int[] arr2, int d) {
        int res = 0;

        for (int i = 0; i < arr1.length; i++) {

            for (int j = 0; j < arr2.length; j++) {

                if (Math.abs(arr1[i] - arr2[j]) <= d) {
                    break;
                }
                if (j == arr2.length - 1) {
                    if (Math.abs(arr1[i] - arr2[j]) > d) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
}
